package com.sjc.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/**
 * 桶排序，解决计数排序的局限性（最大值和最小值相差很大；只能用于正整数）
 *
 * @author by SangJiacun
 * @Date 2020/5/12 18:48
 */
public class BucketSort {

    public static void main(String[] args) {
        double[] array = new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};
        double[] doubles = bucketSort(array);
        System.out.println(Arrays.toString(doubles));
    }

    private static double[] bucketSort(double[] array){
        // 1.得到数列的最大值和最小值，并算出差值d
        double max = array[0];
        double min = array[0];
        for(int i=0; i< array.length; i++){
            if(max < array[i]){ max = array[i]; }
            if(min > array[i]){min = array[i]; }
        }

        double d = max - min;

        // 2. 初始化桶
        int bucketNum = array.length;
        ArrayList<LinkedList<Double>> bucketList = new ArrayList<LinkedList<Double>>();
        for(int i=0; i< bucketNum; i++){
            bucketList.add(new LinkedList<Double>());
        }

        // 3. 遍历原始数组，将每个元素放入桶中
        for(int i=0; i< array.length; i++){
            int num = (int)((array[i] - min)  * (bucketNum-1) / d);
            bucketList.get(num).add(array[i]);
        }

        // 4.对每个桶内部进行排序
        for(LinkedList<Double> bucket : bucketList){
            Collections.sort(bucket);
        }

        // 5.输出全部元素
        double[] sortArr = new double[array.length];
        int index = 0;
        for(LinkedList<Double> bucket : bucketList){
            for(double value : bucket){
                sortArr[index] = value;
                index++;
            }
        }
        return sortArr;
    }
}
